package com.cby.leetcode.链表.LC142;

import com.cby.leetcode.链表.LC148.LC148;
import com.cby.leetcode.链表.LC206.LC206;

public class LC142 {

    /**
     * 快慢指针找环入口
     * 设 非环长 a
     *    环长  b
     *    慢指针 c  快 2c
     *
     *    则有 c = 2c - c = k * b ; k为快指针走的圈数
     *    那么慢指针在环中走的距离： c - a = k * b - a
     *    则再让慢指针走a步在环中走的距离为 k * b 为环长k倍，正好回到环起点
     *    不知道a为多少，则让head和慢指针一起走a步，正好在环起点相遇
     */


    // 定义链表节点类
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }


    public class Solution {
        public ListNode detectCycle(ListNode head) {

            ListNode fast = head;
            ListNode slow = head;

            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
                    while (slow != head){
                        slow = slow.next;
                        head = head.next;
                    }

                    return slow;
                }
            }

            return null;

        }
    }


}
